/**
 * 2017年7月31日
 */
package leetcode;

import java.util.*;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
/**
 * @author Alex
 *
 */
public class WordBreakII {
	static Logger logger = LoggerFactory.getLogger(WordBreakII.class);
	public static void main(String[] args) {
		Set<String> set = Sets.newHashSet();
		set.add("cat");
		set.add("cats");
		set.add("and");
		set.add("sand");
		set.add("dog");		
		wordBreak("catsanddog", set).forEach(System.out::println);
	}
	public static List<String> wordBreak(String s,Set<String> wordDict){
		boolean f [] = new boolean[s.length()+1];
		boolean [][] prev = new boolean[s.length()+1][s.length()];
		f[0] = true;

		for(int i=1;i<=s.length();i++){
			for(int j = i-1;j>=0;j--){
				logger.info("{},{}",i,j);				
				if(f[j] && wordDict.contains(s.substring(j,i))){
					f[i] = true;
					prev[i][j] = true;
				}
			}
		}
		List<String> result = Lists.newArrayList();
		List<String> path = Lists.newArrayList();
		genPath(s, prev,s.length(), path, result);
		return result;
	}
	public static void genPath(String s,boolean [][] prev,int cur,List<String>path,List<String>result){
		if(cur == 0){
			StringBuilder sb = new StringBuilder();
			for(int i=path.size()-1;i>=0;--i){
				sb.append(path.get(i)).append(' ');
			}
			sb.deleteCharAt(sb.length()-1);
			result.add(sb.toString());
		}
		for( int i = 0;i<s.length();i++){
			if(prev[cur][i]){
				path.add(s.substring(i,cur));
				genPath(s, prev, i, path, result);
				path.remove(path.size()-1);
			}
		}
	}
}
